package com.xieyong.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode2359 {
    public static void main(String[] args) {
        Leetcode2359 test = new Leetcode2359();
        int[] edges = {5,3,1,0,2,4,5};
        int node1 = 3;
        int node2 = 2;
        int i = test.closestMeetingNode(edges, node1, node2);
        System.out.println(i);
    }

//   方法超时
//    public int closestMeetingNode(int[] edges, int node1, int node2) {
//        List<Integer> list = new ArrayList<>();
//        list.add(node1);
//        int head = edges[node1];
//        while (!list.contains(head) && head != -1) {
//            list.add(head);
//            head = edges[head];
//        }
////        System.out.println(list);
//        int head2 = node2;
//        int count = 0;
//        int mindistance = Integer.MAX_VALUE;
//        int result = Integer.MAX_VALUE;
//        List<Integer> list2 = new ArrayList<>();
//        do{
////            System.out.println(" __________ " + head2);
//            list2.add(head2);
//            if(list.contains(head2)) {
//                int distance = Math.max(count, list.indexOf(head2));
////                System.out.println(mindistance + "--------------- " + distance);
//                if(distance < mindistance) {
//                    result = head2;
//                    mindistance = distance;
//                } else if(distance == mindistance) {
//                    result = Math.min(result, head2);
//                }
//            }
//            count++;
//            head2 = edges[head2];
//        }while (!list2.contains(head2) && head2 != -1);
//        return result == Integer.MAX_VALUE ? -1 : result;
//    }

//   又超时了
//    public int closestMeetingNode(int[] edges, int node1, int node2) {
//        List<Integer> list1 = getlist(edges, node1);
//        List<Integer> list2 = getlist(edges, node2);
//        int res = -1;
//        int mindist = Integer.MAX_VALUE;
//        for(int i = 0; i < edges.length; i++) {
//            int dis1 = list1.indexOf(i);
//            int dis2 = list2.indexOf(i);
//            if(dis1 != -1 && dis2 != -1) {
//                int maxdis = Math.max(dis1,dis2);
//                if(maxdis < mindist) {
//                    res = i;
//                    mindist = maxdis;
//                } else if(maxdis == mindist) {
//                    res = Math.min(res, i);
//                }
//            }
//        }
//        return res;
//
//    }
//
//    public List<Integer> getlist (int[] edges, int node) {
//        List<Integer> list = new ArrayList<>();
//        while (!list.contains(node) && node != -1) {
//            list.add(node);
//            node = edges[node];
//        }
//        return list;
//    }


public int closestMeetingNode(int[] edges, int node1, int node2) {
    int n = edges.length;
    int[] d1 = get(edges, node1);
    int[] d2 = get(edges, node2);

    int res = -1;
    for (int i = 0; i < n; i++) {
        if (d1[i] != -1 && d2[i] != -1) {
            if (res == -1 || Math.max(d1[res], d2[res]) > Math.max(d1[i], d2[i])) {
                res = i;
            }
        }
    }
    return res;
}

    private int[] get(int[] edges, int node) {
        int n = edges.length;
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        int distance = 0;
        while (node != -1 && dist[node] == -1) {
            dist[node] = distance++;
            node = edges[node];
        }
        return dist;
    }
}
